# 1. 的 cache 版
from typing import List

# 50+
class Solution:
    def __init__(self):
        self.cache = {}

    def minPathSum(self, grid: List[List[int]]) -> int:
        w = len(grid)
        h = len(grid[0])
        return self.minPC(grid, w - 1, h - 1)

    def minPC(self, grid: List[List[int]], x, y):
        t = (x, y)
        if t in self.cache:
            return self.cache[t]
        else:
            r = self.minP(grid, x, y)
            self.cache[t] = r
            return r

    def minP(self, grid: List[List[int]], x, y):
        w = len(grid)
        h = len(grid[0])
        curr = grid[x][y]
        if x == 0 and y == 0:
            return curr
        if x > 0 and y > 0:
            return min(self.minPC(grid, x - 1, y) + curr,
                       self.minPC(grid, x, y - 1) + curr)
        if x > 0 and y == 0:
            return self.minPC(grid, x - 1, y) + curr
        if x == 0 and y > 0:
            return self.minPC(grid, x, y - 1) + curr


solu = Solution()
# print(solu.minPathSum([
#   [1,3,1],
#   [1,5,1],
#   [4,2,1]
# ]))

print(solu.minPathSum([
    [1, 2, 3],
    [4, 5, 6]
]))
